package name.huzhenbo.java.algorithm.talent;

/**
 * Thoughts:
 * <p/>
 * a1 a2 a3 a4 a5
 * <p/>
 * if   a3 + a5 > target
 * then move a5 to a4
 * if   a3 + a4 > target
 * question: why should move a4 move to a3, but not move a3 back to a2?
 * because a2 + a4 < a2 + a5, and a2 + a5 < s (otherwise how can i reach a3?), so a2 + a4 < s
 * <p/>
 * Another thoughts:
 * when i = 2 and a2 + a5 > s, move a5 to a4
 * and a2 + a4 < s, then it means there's no value in the array equals s - a2 (which means ax + a2 = s), so a2 could be abandoned
 * <p/>
 * If input is unordered, how to find the pair under time complexity: n?
 * loop the array, for each ai, try to find the s - ai in the array under constant complexity.
 * <p/>
 * *  Use hash table.
 */
class PairFinder {

    // logn
    public boolean isPairExist(int[] input, int target) {
        int i = 0;
        int j = input.length - 1;
        while (i < j) {
            int currentSum = input[i] + input[j];
            if (currentSum > target) {
                j--;
            } else if (currentSum < target) {
                i++;
            } else {
                return true;
            }
        }
        return false;
    }

    // find 3 items, where ai + aj + ak = target
    // which means find ai + aj = target - ak.
    public boolean isTriExist(int[] input, int target) {
        for (int k = 0; k < input.length; k++) {
            int i = 0;
            int j = input.length - 1;
            int currentTarget = target - input[k];
            while (i < j) {
                // skip k
                if (i == k || j == k) {
                    if (i == k) i++;
                    else j--;
                    // re-compare i and j
                    continue;
                }
                int currentSum = input[i] + input[j];
                if (currentSum > currentTarget) {
                    j--;
                } else if (currentSum < currentTarget) {
                    i++;
                } else {
                    return true;
                }
            }
        }
        return false;
    }
}
